package leetcode_链表;

import general_class.ListNode;

/**
 * 两数相加
 * 算法：递归
 *
 * @author origin
 */
public class _02 {

    public static void main(String[] args) {
        ListNode n1 = new ListNode(2, new ListNode(4, new ListNode(3, null)));
        ListNode n2 = new ListNode(5, new ListNode(6, new ListNode(4, null)));
        ListNode n3 = new ListNode(2, new ListNode(4, new ListNode(9, null)));
        ListNode n4 = new ListNode(5, new ListNode(6, new ListNode(4, new ListNode(9, null))));
        ListNode n = new _02().addTwoNumbers_20220310(n3, n4);
        while (n != null) {
            System.out.print(n.val + " ");
            n = n.next;
        }
//        ListNode node = new _02().addTwoNumbers(n1, n2);
//        while (node != null) {
//            System.out.print(node.val + " ");
//            node = node.next;
//        }
    }

    public ListNode addTwoNumbers_20220310(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode ans = l1, pre = null;
        int carry = 0;
        while (l1 != null && l2 != null) {
            int tmp = l1.val + l2.val + carry;
            l1.val = tmp % 10;
            if (tmp >= 10) carry = 1;
            else carry = 0;
            pre = l1;
            l1 = l1.next;
            l2 = l2.next;
        }
        if (l1 == null && l2 != null) {
            pre.next = l2;
            l1 = pre.next;
        } else if (l1 == null && carry == 1) pre.next = new ListNode(1);
        while (l1 != null) {
            int tmp = l1.val + carry;
            l1.val = tmp % 10;
            if (tmp >= 10) carry = 1;
            else carry = 0;
            pre = l1;
            l1 = l1.next;
        }
        if (carry == 1) pre.next = new ListNode(1);
        return ans;
    }

    public ListNode addTwoNumbers_iteration(ListNode l1, ListNode l2) {
        ListNode ans = new ListNode(), cur = ans;
        int carry = 0;
        while (l1 != null || l2 != null || carry == 1) {
            int sum = 0;
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            sum += carry;
            if (sum >= 10) carry = 1;
            else carry = 0;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
        }
        return ans.next;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode ans = new ListNode();
        sum(l1, l2, ans, 0);
        return ans;
    }

    public void sum(ListNode l1, ListNode l2, ListNode ans, int carry) {
        int sum = carry;
        carry = 0;
        if (l1 != null) {
            sum += l1.val;
        }
        if (l2 != null) {
            sum += l2.val;
        }
        if (sum >= 10) {
            carry = 1;
            sum -= 10;
        }
        ans.val = sum;
        ListNode n1 = l1 == null ? null : l1.next;
        ListNode n2 = l2 == null ? null : l2.next;
        if (n1 == null && n2 == null) {
            if (carry > 0) {
                ans.next = new ListNode();
                ans.next.val = carry;
            }
            return;
        }
        ans.next = new ListNode();
        sum(n1, n2, ans.next, carry);
    }
}
